package alogrithm;

import java.util.Arrays;
import java.util.Random;


/**
 * @author lbw
 * @version 1.0
 * @date 2021/9/2 22:16
 */
public class RandomQuickSort {

    private static final Random random = new Random();

    public static void main(String[] args) {
        int[] a = new int[]{4, 1, 6, 2, 7, 9, 8, 3, 5};
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    private static void quickSort(int[] a, int l, int r) {
        if (l < r) {
            int q = randomPartition(a, l, r);
            quickSort(a, l, q - 1);
            quickSort(a, q + 1, r);
        }
    }

    private static int randomPartition(int[] a, int l, int r) {
        int index = random.nextInt(r - l + 1) + l;

        swap(a, l, index);
        return partition(a, l, r);
    }

    private static int partition(int[] a, int l, int r) {

        int x = a[l];
        int low = l;
        int high = r;

        while (low < high) {
            while (low < high && a[high] >= x) {
                high--;
            }
            while (low < high && a[low] <= x) {
                low++;
            }
            if (low < high) {
                swap(a, low, high);
            }

        }
        a[l] = a[low];
        a[low] = x;
        return low;
    }

    private static void swap(int[] a, int low, int high) {

        int tmp = a[low];
        a[low] = a[high];
        a[high] = tmp;
    }
}
